import java.util.ArrayList;


public class TreeNodeTest {

	static String inOrder (TreeNode<Integer> r){
		String s= "";
		if(r != null){
			s += inOrder(r.getLeft());
			s += r.toString()+" ";
			s += inOrder(r.getRight());
		}
		return s;
	}
	static String postOrder (TreeNode<Integer> r){
		String s= "";
		if(r != null){
			s += postOrder(r.getLeft());
			s += postOrder(r.getRight());
			s += r.toString()+" ";
		}
		return s;
	}
	static String preOrder (TreeNode<Integer> r){
		String s= "";
		if(r != null){
			s += r.toString()+" ";
			s += preOrder(r.getLeft());
			s += preOrder(r.getRight());
		}
		return s;
	}
	static ArrayList<String> levelOrder(TreeNode<Integer> r, int i, ArrayList<String> a){
		String s;
		if (r != null){
			while(i>=a.size())
				a.add("");
			s = a.get(i) + r.toString()+ " ";
			a.remove(i);
			a.add(i, s);
			levelOrder(r.getLeft(),  i+1,a);
			levelOrder(r.getRight(), i+1,a);
			
		}
		return a;
	}
	static String levelOrder(TreeNode<Integer> r){
		String s="";
		ArrayList<String> a = new ArrayList<String>();
		a = levelOrder(r,0,a);
		for (int i=0; i<a.size();i++)
			s += a.get(i);
		return s;
	}
	public static void main(String[] args){
		TreeNode<Integer> root = new TreeNode<Integer>(8, 
									new TreeNode<Integer>(4, 
										new TreeNode<Integer>(6),
										new TreeNode<Integer>(11)),
									new TreeNode<Integer>(1,
										new TreeNode<Integer>(5),
										new TreeNode<Integer>(7)));
		System.out.println(inOrder(root));
		System.out.println(preOrder(root));
		System.out.println(postOrder(root));
		System.out.println(levelOrder(root));

		

	}
}
